/**
 * 题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。
 * 示例:输入: [10,9,2,5,3,7,101,18]
 * 输出: 4
 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 *
 */

/**
 * 思路分析
 * 关注到序列中元素的索引，尝试寻找不同索引对应的元素之间的关系、
 * 并以索引为线索去构造一维或二维的状态数组。
 * 拿“最长上升子序列”这个问题分支来说，
 * 这里我们关注到的就是“以序列中第 i 个元素为结尾的前i个元素的状态”。
 * 若第i + 1,比i的元素大，则追加原序列得到新序列
 * 若i+1比i的元素小，则维持不变
 */

// 入参是一个数字序列
const lengthOfLIS = function (nums) {
  // 缓存序列的长度
  const len = nums.length;
  // 处理边界条件
  if (!len) {
    return 0;
  }
  // 初始化数组里面每一个索引位的状态值
  const dp = new Array(len).fill(1);
  // 初始化最大上升子序列的长度为1
  let maxLen = 1;
  // 从第2个元素开始，遍历整个数组
  for (let i = 1; i < len; i++) {
    // 每遍历一个新元素，都要“回头看”，看看能不能延长原有的上升子序列
    for (let j = 0; j < i; j++) {
      // 若遇到了一个比当前元素小的值，则意味着遇到了一个可以延长的上升子序列，故更新当前元素索引位对应的状态
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    // 及时更新上升子序列长度的最大值
    if (dp[i] > maxLen) {
      maxLen = dp[i];
    }
  }
  // 遍历完毕，最后到手的就是最大上升子序列的长度
  return maxLen;
};
let arr =  [10,9,2,5,3,7,101,18]
console.log(lengthOfLIS(arr));
